<!doctype html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport"
        content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>
<script>
  const arr = [21, 12, 3, 45, 26, 44]

  /* 冒泡 */
  function bubbleSort(arr) {
    for (let i = 1; i < arr.length; i++) {
      for (let j = 0, temp; j < arr.length - i; j++) {
        if (arr[j] > arr[j + 1]) {
          // temp = arr[j];
          // arr[j] = arr[j+1];
          // arr[j+1] = temp;

          // arr[j] = arr[j] + arr[j+1];
          // arr[j+1] = arr[j] - arr[j+1];
          // arr[j] = arr[j] - arr[j+1];

          arr[j] = [arr[j + 1], arr[j + 1] = arr[j]][0]
        }

      }
    }
    return arr;

  }

  // console.log(bubbleSort(arr));


  /* 快速 */
  function quickSort(arr) {
    if (arr.length <= 1) {
      return arr
    }
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < pivot) {
        left.push(arr[i])
      }
      if (arr [i] > pivot) {
        right.push(arr[i])
      }

    }
    // return quickSort(left).concat([pivot],quickSort(right));
    return [...quickSort(left), pivot, ...quickSort(right)]


  }

  // console.log(quickSort(arr));

  /* 爬楼算法（斐波那契数列） */
  // 暴力迭代，这种方法的算法复杂度是O(2^n)
  function stair(n) {
    if (n === 0) {
      return 1;
    } else if (n < 0) {
      return 0;
    } else {
      return stair(n - 1) + stair(n - 2)
    }
  }

  // 缓存计算好的值（for 循环）
  function stair_2(n) {
    const arr = new Array(n);

    for (let i = 1; i <= n; i++) {
      if (i < 3) {
        arr[i - 1] = i;
      } else {
        arr[i - 1] = arr[i - 2] + arr[i - 3];
      }

    }

    return n <= 0 ? 0 : arr[n - 1];

  }

  // console.log(stair(40))
  // console.log(stair_2(14))


  // 找零（动态规划）
  class Change {
    constructor(changeType) {
      this.changeType = changeType
      this.cache = {}
    }

    makeChange(amount) {
      let min = []
      if (!amount) {
        return []
      }
      if (this.cache[amount]) { // 读缓存
        return this.cache[amount]
      }

      for (let i = 0; i < this.changeType.length; i++) {
        const leftAmount = amount - this.changeType[i];
        let newMin;
        if (leftAmount >= 0) {
          console.log(leftAmount, '===leftAmount')
          newMin = this.makeChange(leftAmount) // 这⼀句是动态规划的提现
        }
        if (leftAmount >= 0
          && (newMin.length < min.length - 1 || !min.length)) { // 如果存在更少的找零硬币数, 则执⾏后⾯语句
          min = [this.changeType[i]].concat(newMin)
          console.log(min, '----min')
        }
      }
      return this.cache[amount] = min
    }
  }

  const change = new Change([1, 5, 10, 20, 50, 100]);
  change.makeChange(6)

  // 找零（贪心算法）
  class Change2 {
    constructor(changeType) {
      this.changeType = changeType.sort((r1, r2) => r2 - r1);
    }

    makeChange(amount) {
      const arr = []
      for (let i = 0; i < this.changeType.length; i++) {
        while (amount - this.changeType[i] >= 0) {
          arr.push(this.changeType[i])
          amount = amount - this.changeType[i]
        }
      }
      return arr
    }
  }

  const change2 = new Change2([1, 5, 10, 20, 50, 100]);
  change2.makeChange(11)

</script>
</body>
</html>
